//
// Description: 5269. 从栈中取出 K 个硬币的最大面值和
// Created by Loading on 2022/3/27.
//

#include <bits/stdc++.h>

using namespace std;

/* 背包问题 */
int maxValueOfCoins(vector<vector<int>> &piles, int k) {
    vector<int> dp(k + 1);
    int n = piles.size();
    for (int i = 0; i < n; ++i) {
        int len = piles[i].size();
        // 前缀和
        vector<int> pre(len + 1);
        for (int j = 0; j < len; ++j) {
            pre[j + 1] = pre[j] + piles[i][j];
        }

        /* 逆序遍历，若顺序遍历，则dp[j - l]的值已被更新过，这里需要取未更新过的数值 */
        for (int j = k; j >= 0; --j) {
            for (int l = 1; j >= l && l <= len; ++l) {
                dp[j] = max(dp[j], dp[j - l] + pre[l]);
            }
        }
    }

    return dp[k];
}

int main() {
    vector<vector<int>> piles{{100},
                              {100},
                              {100},
                              {100},
                              {100},
                              {100},
                              {1, 1, 1, 1, 1, 1, 700}};
    int k = 7;
    auto res = maxValueOfCoins(piles, k);
    cout << res << endl;

    return 0;
}